/*
 * @lc app=leetcode.cn id=51 lang=golang
 *
 * [51] N 皇后
 */

// 2. 这个思路是有一个大的矩阵，选中【0， 0】的话，就把选中这个节点的所在的列，右下斜着的列，左下斜着的列都删掉
// 这样矩阵会越来越小，如果能到最后一行就是符合的，如果还没到最后一行的时候那一行的size()变成0，就不符合，结束递归。
// qMap : 1, 2, 3, 4
//        1, 2, 3, 4
//        1, 2, 3, 4
//        1, 2, 3, 4
//
// @lc code=start
func solveNQueens(n int) [][]string {
	res := [][]int{}
	qMap := make([][]int, n)
	for i := 0; i < n; i++ {
		def := make([]int, 0)
		for j := 0; j < n; j++ {
			def = append(def, j)
		}
		qMap[i] = def
	}
	var removeElements func(qMap [][]int, arr []int, row int)
	removeElements = func(qMap [][]int, arr []int, row int) {
		for i := 0; i < len(qMap[row]); i++ {
			rr := cloneMap(qMap)
			e := rr[row][i]
			tempArr := make([]int, len(arr))
			copy(tempArr, arr)
			tempArr = append(tempArr, e)
			for j, x := 1, row+1; x < n; j++ {
				ints := rr[x]
				ints = removeElement(ints, e-j)
				ints = removeElement(ints, e)
				ints = removeElement(ints, e+j)
				rr[x] = ints
				x++
			}
			if row == n-1 {
				res = append(res, tempArr)
				return
			}

			if len(rr[row+1]) != 0 {
				removeElements(rr, tempArr, row+1)
			}
			//arr = make([]int, 0)
		}
	}
	removeElements(qMap, make([]int, 0), 0)
	r := convert(res)
	return r
}

func cloneMap(mm [][]int) [][]int {
	res := make([][]int, len(mm))
	for i, ints := range mm {
		dd := make([]int, len(ints))
		copy(dd, ints)
		res[i] = dd
	}
	return res
}

func removeElement(arr []int, value int) (res []int) {
	for i := 0; i < len(arr); i++ {
		if arr[i] == value {
			res = append(arr[:i], arr[i+1:]...)
			return
		}
	}
	res = arr
	return
}

func convert(arr [][]int) (res [][]string) {
	for _, ints := range arr {
		board := []string{}
		for i := 0; i < len(ints); i++ {
			row := make([]byte, len(ints))
			for j := 0; j < len(ints); j++ {
				row[j] = '.'
			}
			row[ints[i]] = 'Q'
			board = append(board, string(row))
		}
		res = append(res, board)
	}
	return
}

// @lc code=end

// 1. 回溯
// board []int的下标代表行，下标对应的值代表列
// @lc code=start
func solveNQueens(n int) (ans [][]string) {
	var recursion func(board []int, row int)
	recursion = func(board []int, row int) {
		if row == n {
			ans = append(ans, convert(board))
			return
		}

		for i := 0; i < n; i++ {
			if isUsed(board, i) {
				continue
			}

			board = append(board, i)
			recursion(board, row+1)
			board = board[:len(board)-1]
		}
	}
	recursion([]int{}, 0)
	return
}

func isUsed(board []int, column int) bool {
	for i := 0; i < len(board); i++ {
		if column == board[i] {
			return true
		}
	}

	for i, j := len(board)-1, 1; i >= 0; i, j = i-1, j+1 {
		if board[i] == column-j || board[i] == column+j {
			return true
		}
	}
	return false
}

func convert(board []int) (ans []string) {
	for i := 0; i < len(board); i++ {
		row := make([]byte, len(board))
		for j := 0; j < len(board); j++ {
			if j != board[i] {
				row[j] = '.'
			} else {
				row[j] = 'Q'
			}
		}
		ans = append(ans, string(row))
	}
	return
}

// @lc code=end

